package 单周赛.history;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *
 */
public class 第284场单周赛 {

    public static void main(String[] args) {

        int[] nums = {3, 4, 9, 1, 3, 9, 5};
        System.out.println(findKDistantIndices(nums, 9, 1));

        int[][] arts = {{0, 0, 0, 0}, {0, 1, 1, 1}};
        int[][] dig = {{0, 0}, {0, 1}, {1, 1}};
        System.out.println(digArtifacts(2, arts, dig));

        int[] nums3 = {35, 43, 23, 86, 23, 45, 84, 2, 18, 83, 79, 28, 54, 81, 12, 94, 14, 0, 0, 29, 94, 12, 13, 1, 48, 85, 22, 95, 24, 5, 73, 10, 96, 97, 72, 41, 52, 1, 91, 3, 20, 22, 41, 98, 70, 20, 52, 48, 91, 84, 16, 30, 27, 35, 69, 33, 67, 18, 4, 53, 86, 78, 26, 83, 13, 96, 29, 15, 34, 80, 16, 49};

        int[] n = {91, 98};
        System.out.println(maximumTop(n, 2));
    }


    /**
     * 6031. 找出数组中的所有 K 近邻下标
     * 用set去除
     *
     * @param nums
     * @param key
     * @param k
     * @return
     */
    public static List<Integer> findKDistantIndices(int[] nums, int key, int k) {
        Set<Integer> set = new HashSet<>();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == key) {
                int left = 0;
                if (i - k > 0) {
                    left = i - k;
                }
                for (int j = left; j <= i + k && j < nums.length; j++) {
                    if (set.add(j)) {
                        list.add(j);
                    }
                }
            }
        }
        return list;
    }

    /**
     * 5203. 统计可以提取的工件
     * 思路
     * 对于每一件工件，用不重复的数字进行标记
     * 挖掘的时候将挖到的工件置为0，
     * 那么剩下的工件即为不能够被提取的
     * 总工件数-不能提取的数量即为答案
     * 注意：一个工件可能有多个块需要对工件进行去除！！！
     *
     * @param n
     * @param artifacts
     * @param dig
     * @return
     */
    public static int digArtifacts(int n, int[][] artifacts, int[][] dig) {
        int artifactMark = 1;
        int[][] grid = new int[n][n];
        for (int[] artifact : artifacts) {
            // 不同行不同列，有四个格子
            int row1 = artifact[0];
            int column1 = artifact[1];
            int row2 = artifact[2];
            int column2 = artifact[3];
            if (row1 != row2 && column1 != column2) {
                grid[row1][column1 + 1] = artifactMark;
                grid[row2][column2 - 1] = artifactMark;
            } else if (row1 == row2) {  //同行，可能中间隔着两个格子
                for (int column = column1 + 1; column < column2; column++) {
                    grid[row1][column] = artifactMark;
                }
            } else if (column1 == column2) {
                for (int row = row1 + 1; row < row2; row++) {
                    grid[row][column1] = artifactMark;
                }
            }
            grid[row1][column1] = artifactMark;
            grid[row2][column2] = artifactMark;
            artifactMark++;
        }

        for (int[] d : dig) {
            grid[d[0]][d[1]] = 0;
        }

        Set<Integer> set = new HashSet<>();
        for (int row = 0; row < grid.length; row++) {
            for (int column = 0; column < grid[0].length; column++) {
                if (grid[row][column] != 0) {
                    set.add(grid[row][column]);
                }
            }
        }
        return artifacts.length - set.size();
    }

    /**
     * 5227. K 次操作后最大化顶端元素
     * 如果k=0，直接返回栈顶
     * 如果nums.length=1，
     * k为偶数，那么返回栈顶元素（注意：过程中栈允许为空！！！）
     * k为奇数，栈一定为空，反回-1
     * <p>
     * 对于一般情况
     * 我们先贪心的将k-1个元素全部取出
     * 最后一步，
     * 选择删除，第k+1个元素为栈顶元素
     * 选择添加，从签名k-1个元素中取出最大元素
     *
     * @param nums
     * @param k
     * @return
     */
    public static int maximumTop(int[] nums, int k) {
        if (k == 0 || nums.length == 1 && k % 2 == 0) {
            return nums[0];
        }
        if (nums.length == 1 && k % 2 != 0) {
            return -1;
        }
        int max = -1;
        for (int i = 0; i < k - 1 && i < nums.length; i++) {
            max = Math.max(max, nums[i]);
        }
        if (k < nums.length) {
            max = Math.max(max, nums[k]);
        }
        return max;
    }

}
